<?xml version="1.0" encoding="UTF-8" ?>
<!DOCTYPE html
  PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN"
  "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
  <head>
    <meta http-equiv="Content-Type" content="text/html" />
    <meta name="keywords" content="tiny mt" />
    <title>Tiny Mersenne Twister (TinyMT)</title>
    <style type="text/css">
      TABLE.numeric TD {text-align:right}
      DD.gray {color:gray}
      body {margin-right:10%;margin-left:10%}
    </style>
  </head>
  <body>
    <h2>Tiny Mersenne Twister</h2>
    <h2>READ ME FIRST</h2>

    <p>
      There are two kinds of programs in this archive file.  One
      is <strong>TinyMT</strong> and another
      is <strong>TinyMTDC</strong>.  TinyMT is a pseudorandom number
      generator, while TinyMTDC is a parameter-set generator for TinyMT.
    </p>

    <h2>TinyMT</h2>

    <p>
      TinyMT is a small-sized pseudorandom number generator, compared
      with Mersenne Twister or WELL RNG. tinymt32 uses 16 bytes for
      its internal state vector and 12 bytes for its parameters, and
      tinymt64 uses 16 bytes for its internal state vector and 16 bytes
      for its parameters.
      Pseudorandom number sequences generated by TinyMT has a period
      of 2<sup>127</sup>-1.
    </p>

    <ul>
      <li>There are two types of TinyMT: tinymt32 and tinymt64.
	tinymt32 outputs 32-bit unsigned integers and single precision
	floating point numbers. On the other hand, tinymt64
	outputs 64-bit unsigned integers and double precision floating
	point numbers.
      </li>
      <li>TinyMT is not designed for a particular hardware. It will run on
	many types of hardware, because of its small size.
      </li>
      <li>TinyMT generates pseudorandom numbers using two functions:
	a state transition function and an output function.
	The state transition function is an F<sub>2</sub>-linear
	function whose characteristic polynomial is irreducible of degree 127.
	The output function is not F<sub>2</sub>-linear,
	but almost F<sub>2</sub>-linear. The output function is composed
	from several F<sub>2</sub>-linear functions, except for one
	non F<sub>2</sub>-linear operation, namely an addition as integers
	modulo 2<sup>32</sup> (or mod 2<sup>64</sup> for tinymt64) which
	replaces an F<sub>2</sub>-vector addition.
      </li>
      <li>
	TinyMT passes Bigcrush test suite of TESTU01, which is one of the
	severest tests against pseudorandom number generators. To be precise,
	we used 10 parameter sets of tinymt32, and used 10 seeds for
	each parameters, so we tested total 100 sequences using Bigcrush
	test suite. Some sequences fails one or two tests in the test
	suite, but the test suite has 160 tests, even the true random
	sequence will possibly fail in some tests. We checked the test
	that TinyMT failed in (with parameter sets and seeds), and we
	could not find a systematic deviation when seeds are changed.
	Thus, we conclude that TinyMT passed the Bigcrush test suite.
      </li>
      <li>
	There is a notion of the dimension of equidistribution to v-bit
	accuracy (k(v)). High values of k(v) shows high-dimensional
	uniformity up to the v-bit precision. In the case of TinyMT,
	we can not compute these values because of the non-linearity
	of the output function. Instead, we compute k(v)s for a
	linearized output function, and search for parameters with
	high values of k(v). They are close to the theoretical
	upper bound (dimension of the internal space / v), but far
	smaller than Mersenne Twister 19937. For example, k(32) for
	tinymt32 is smaller than 4, while k(32) for Mersenne Twister 19937
	is 623.
      </li>
      <li>
	TinyMT is not designed to replace Mersenne Twister.
	In some applications, namely, hardware implementation or highly
	parallel environment, the large state size (19937 bits) of
	Mersenne Twister may be an obstruction for implementation.
	TinyMT is designed for such situation, with small state size
	and good randomness for that size of internal state.
      </li>
    </ul>

    <h3>Requirement</h3>
    <p>TinyMT is written in C language, and it uses stdint.h and inttypes.h
      of c99.
    </p>
    <ul>
      <li>gcc supports c99, use std=c99 option.</li>
      <li>Visual Studio C/C++ does not support c99, but you can get
	stdint.h and inttypes.h for Visual Studio from
	<a href="http://code.google.com/p/msinttypes/">msinttypes</a>
	in Google code.
      </li>
    </ul>

    <h3>Compile and check</h3>
    <ol>
      <li><b>cd tinymt</b></li>
      <li><b>make all</b></li>
      <li>Executable file check32 and check64 are made</li>
      <li>To check these programs:
	<blockquote>
	check32 8f7011ee fc78ff1f 3793fdff &gt; tmp32.txt<br/>
	diff tmp32.txt check32.out.txt<br/>
	check64 fa051f40 ffd0fff4 58d02ffeffbfffbc &gt; tmp64.txt<br/>
	diff tmp64.txt check64.out.txt
	</blockquote>
	O.K. if diff does not show differences</li>
    </ol>

    <h2>TinyMTDC</h2>

    <p>TinyMTDC is a parameter generator for TinyMT.
      A user specifies an ID and the number of sets of parameters to be
      generated. TinyMTDC can generate more than 2<sup>16</sup> distinct set
      of parameters (with ID embedded) to be used as parameters in TinyMT.
    </p>
    <ul>
      <li>There are two types of TinyMTDC: tinymt32dc creates
      parameter sets for tinymt32, and tinymt64dc creates those
      for tinymt64.</li>
      <li>TinyMTDC generates specified number of parameters for
	each ID. Maximum number of parameters for each id will be
	less than 2<sup>28</sup>.</li>
      <li>The characteristic polynomials of TinyMT using parameter
	set generated by TinyMTDC is different when ID used by
	TinyMTDC is different.</li>
    </ul>

    <h3>Required Library</h3>
    <p>TinyMTDC is written in C++ language using template features.</p>
    <ul>
      <li>Victor Shoup's <a href="http://shoup.net/ntl/">
	  NTL: A Library for doing Number Theory</a>.</li>
      <li><a href="http://www.boost.org/">C++ TR1 Libraries</a>.
	(g++ ver. 4.0 or later)</li>
      <li>(Only g++ 4.2.1 and icc 11.1 are tested)</li>
    </ul>

    <h3>Compile</h3>
    <ol>
      <li>change directory to <b>dc/src</b></li>
      <li><b>make all</b></li>
      <li>tinymt32dc, tinymt64dc and getid are created</li>
    </ol>

    <h3>Programs and usage</h3>
    <dl>
      <dt>
	tinymt32dc [-v] [-c count] [-s seed_string] [-f outputfile] ID<br/>
	tinymt64dc [-v] [-c count] [-s seed_string] [-f outputfile] ID
      </dt>
      <dd>These two programs create parameter sets for tinymt32 and tinymt64.
	<ul>
	  <li>argument (required)<br/>
	    <dl>
	      <dt>ID</dt>
	      <dd>ID should be a decimal number such that
		0 &lt;= ID &lt; 2<sup>32</sup><br/>
		For different ID's, the
		generated random number sequences are highly independent.
		(Mathematically saying, the characteristic polynomials
		of the recursion are co-prime to each other.)
	      </dd>
	    </dl>
	  </li>
	  <li>arguments (optional)<br/>
	    <dl>
	      <dt>-v</dt>
	      <dd>Verbose mode for debug. Do not use this.</dd>
	      <dt>-c count</dt>
	      <dd>specify the number of sets of parameters to
		generate.  If omitted, outputs one set of parameters.
		When TinyMTDC is called with <b>-c</b>, an internal
		counter is updated and parameter set are outputted.
		When ID or the internal counter is distinct, the
		characteristic polynomial of the state transition
		function is assured to be distinct. Namely, different
		pairs (ID, internal counter) yields different
		characteristic polynomials.
	      </dd>
	      <dt>-a</dt>
	      <dd>parameter sets are outputted as many as possible.
		if <b>-a</b> is specified <b>-c</b> is ignored.</dd>
	      <dt>-s seq</dt>
	      <dd>set the internal counter to be <b>seq.</b>
		If omitted, its max value is set.</dd>
	      <dt>-m max-defect</dt>
	      <dd>
		the defect at v-bit accuracy means the gap between the
		theoretical upper bound and the realized k(v). The total
		dimension defect is the sum of these values for v=1 to 32
		(for tinymt32) and for v=1 to 64 (for tinymt64).
		If its value is smaller, then the generator is closer to
		the theoretical upper bound. This option set the max
		allowable value of this total dimension defect.
		Parameter sets whose total dimension defect is greater
		than max-defect are discarded. If
		omitted, no parameter sets are discarded. If 0 is specified,
		parameter sets with no defect at any v-bit accuracy will be
		outputted.
	      </dd>
	      <dt>-f filename</dt>
	      <dd>specify output file name. If omitted, standard
		output stream is used.
	      </dd>
	    </dl>
	  </li>
	</ul>
      </dd>
      <dt>getid -b 32|64 mat1 mat2 <br/>
	getid -b 32|64 -r id seq </dt>
      <dd>
	This program calculates the ID and the internal counter from
	parameter sets of TinyMTDC.
	<b>-b</b> option is used to distinguish parameters for tinymt32
	or tinymt64. If omitted -b 32 is assumed.
	When <b>-r</b> is specified, conversely, the program calculates
	the parameters mat1 and mat2 from the ID and the internal counter.<br/>
	This program may be used to resume parameter-set generation: from
	the last (mat1, mat2) generated by TinyMTDC, getid computes the
	corresponding (ID, seq). Then TinyMTDC with -s option for the
	value (seq-1) will resume the previous parameter-set generation,
	as follows.
	<blockquote>
	  $ tail -1 tinymt32dc.0.20.txt<br/>
	  9443129baa73b98c7b097ab82c074d03,32,0,65980cb3,eb38facf,
	  cc3b75ff,59,0<br/>
	  $ ./getid 65980cb3 eb38facf<br/>
	  id:0(0x0)<br/>
	  seq:2147482983(0x7ffffd67)<br/>
	  $ ./tinymt32dc -s 2147482983 0<br/>
	  # charactristic, type, id, mat1, mat2, tmat, weight, delta<br/>
	  9443129baa73b98c7b097ab82c074d03,32,0,65980cb3,eb38facf,cc3b75ff,59,0
	</blockquote>
	</dd>
    </dl>

    <h3>output format of TinyMTDC</h3>
    <p>output of TinyMTDC is Comma Separated Value.
      Here we explain each column.
    </p>
    <table border="1">
      <tr>
	<th>Column or Row</th><th>Description</th>
      </tr>
      <tr>
	<td>The first row</td>
	<td>
	  <pre># charactristic, type, id, mat1, mat2, tmat1, weight, delta</pre>
	  The first row is always the same as above.
	  Each column of the row shows title of columns of following rows.</td>
      </tr>
      <tr>
	<td>1st column: charactristic</td>
	<td>The first column shows the characteristic polynomial of
	  the state transition function. In TinyMT's case,
	  the characteristic polynomial is an irreducible polynomial
	  of degree 127, and its coefficients are 0 or 1.
	  The corresponding hexadecimal number to the coefficients of
	  the polynomial (by descending order, i.e. the constant term comes
	  as LSB) is shown. The first digit of the hexadecimal number
	  is greater than or equals to 8, because its degree is 127,
	  and the last hexadecimal number is odd, because irreducible
	  polynomial (over F<sub>2</sub>) has constant term 1.
	</td>
      </tr>
      <tr>
	<td>2nd column: type</td>
	<td>The second column shows whether this parameter set is for
	  tinymt32 or tinymt64.
	</td>
      </tr>
      <tr>
	<td>3rd column: id</td>
	<td>Third column is the ID specified by user, in command line.
	</td>
      </tr>
      <tr>
	<td>4th column: mat1</td>
	<td>The fourth column shows <b>mat1</b> parameter
	  in the hexadecimal notation.
	</td>
      </tr>
      <tr>
	<td>5th column: mat2</td>
	<td>The fifth column shows <b>mat2</b> parameter in
	  the hexadecimal notation.
	  The parameters <b>mat1</b> and <b>mat2</b> determine
	  the state transition function of the generator.
	</td>
      </tr>
      <tr>
	<td>6th column: tmat</td>
	<td>The sixth column shows <b>tmat</b> parameter
	  in the hexadecimal notation.
	  The parameter <b>tmat</b> determines the output function
	  of the generator.
	</td>
      </tr>
      <tr>
	<td>7th column: weight</td>
	<td>The seventh column shows Hamming weight of the characteristic
	  polynomial. A thumb-nail rule says that the weight value not far
	  from half of the degree of the characteristic polynomial is
	  preferable.
	</td>
      </tr>
      <tr>
	<td>8th column: delta</td>
	<td>The eighth column shows the total dimension defect, which
	  measures the gap from the theoretical upper bounds on the
	  dimensions of equidistribution.
	  0 is the best. TinyMTDC selects the parameter
	  <b>tmat</b> for which delta is small.
	</td>
      </tr>
    </table>

    <h2>LICENSE</h2>
    <pre>
Copyright (c) 2011 Mutsuo Saito, Makoto Matsumoto, Hiroshima
University and The University of Tokyo. All rights reserved.

Redistribution and use in source and binary forms, with or without
modification, are permitted provided that the following conditions are
met:

    * Redistributions of source code must retain the above copyright
      notice, this list of conditions and the following disclaimer.
    * Redistributions in binary form must reproduce the above
      copyright notice, this list of conditions and the following
      disclaimer in the documentation and/or other materials provided
      with the distribution.
    * Neither the name of the Hiroshima University nor the names of
      its contributors may be used to endorse or promote products
      derived from this software without specific prior written
      permission.

THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
"AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
    </pre>
  </body>
</html>
